//给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。 
//
// 回文串 是正着读和反着读都一样的字符串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "aab"
//输出：[["a","a","b"],["aa","b"]]
// 
//
// 示例 2： 
//
// 
//输入：s = "a"
//输出：[["a"]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 16 
// s 仅由小写英文字母组成 
// 
//
// Related Topics 字符串 动态规划 回溯 👍 1536 👎 0


import java.util.ArrayList;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result=new ArrayList<>();
        List<String> tem=new ArrayList<>();
        backTracking(0,s,result,tem);
        return result;
    }

    public void backTracking(int index,String s, List<List<String>> result,  List<String> tem){
        if(index==s.length()){
            result.add(new ArrayList<>(tem));
            return;
        }
        for (int i = index; i <s.length() ; i++) {
            String str=s.substring(index,i+1);
            if(str.length()!=0&&isHuiWen(str)){
                tem.add(str);
            }else {
                continue;
            }
            backTracking(i+1,s,result,tem);
            tem.remove(tem.size()-1);
        }
    }
    public Boolean isHuiWen(String s){
       int left=0;
       int right=s.length()-1;
       while (left<right){
           if(s.charAt(left)!=s.charAt(right)){
               return false;
           }
           left++;
           right--;
       }
       return true;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
